/*-------------------------------------------------------------------------
 *
 * gistutil.c
 *	  Postgres GiST索引访问方法的实用程序例程。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/access/gist/gistutil.c
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <math.h>

#include "access/gist_private.h"
#include "access/htup_details.h"
#include "access/reloptions.h"
#include "catalog/pg_opclass.h"
#include "common/pg_prng.h"
#include "storage/indexfsm.h"
#include "storage/lmgr.h"
#include "utils/float.h"
#include "utils/lsyscache.h"
#include "utils/snapmgr.h"
#include "utils/syscache.h"

/*
 * 将itup向量写入页面，没有自由空间的控制。
 */
void gistfillbuffer(Page fc_page, IndexTuple *fc_itup, int fc_len, OffsetNumber fc_off)
{
	int			fc_i;

	if (fc_off == InvalidOffsetNumber)
		fc_off = (PageIsEmpty(fc_page)) ? FirstOffsetNumber :
			OffsetNumberNext(PageGetMaxOffsetNumber(fc_page));

	for (fc_i = 0; fc_i < fc_len; fc_i++)
	{
		Size		fc_sz = IndexTupleSize(fc_itup[fc_i]);
		OffsetNumber fc_l;

		fc_l = PageAddItem(fc_page, (Item) fc_itup[fc_i], fc_sz, fc_off, false, false);
		if (fc_l == InvalidOffsetNumber)
			elog(ERROR, "failed to add item to GiST index page, item %d out of %d, size %d bytes",
				 fc_i, fc_len, (int) fc_sz);
		fc_off++;
	}
}

/*
 * 检查页面上itup向量的空间
 */
bool gistnospace(Page fc_page, IndexTuple *fc_itvec, int fc_len, OffsetNumber fc_todelete, Size fc_freespace)
{
	unsigned int fc_size = fc_freespace,
				fc_deleted = 0;
	int			fc_i;

	for (fc_i = 0; fc_i < fc_len; fc_i++)
		fc_size += IndexTupleSize(fc_itvec[fc_i]) + sizeof(ItemIdData);

	if (fc_todelete != InvalidOffsetNumber)
	{
		IndexTuple	fc_itup = (IndexTuple) PageGetItem(fc_page, PageGetItemId(fc_page, fc_todelete));

		fc_deleted = IndexTupleSize(fc_itup) + sizeof(ItemIdData);
	}

	return (PageGetFreeSpace(fc_page) + fc_deleted < fc_size);
}

bool gistfitpage(IndexTuple *fc_itvec, int fc_len)
{
	int			fc_i;
	Size		fc_size = 0;

	for (fc_i = 0; fc_i < fc_len; fc_i++)
		fc_size += IndexTupleSize(fc_itvec[fc_i]) + sizeof(ItemIdData);

	/* TODO: 考虑填充因子 */
	return (fc_size <= GiSTPageSize);
}

/*
 * 将缓冲区读入itup向量
 */
IndexTuple *
gistextractpage(Page fc_page, int *fc_len /* 输出 */ )
{
	OffsetNumber fc_i,
				fc_maxoff;
	IndexTuple *fc_itvec;

	fc_maxoff = PageGetMaxOffsetNumber(fc_page);
	*fc_len = fc_maxoff;
	fc_itvec = palloc(sizeof(IndexTuple) * fc_maxoff);
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
		fc_itvec[fc_i - FirstOffsetNumber] = (IndexTuple) PageGetItem(fc_page, PageGetItemId(fc_page, fc_i));

	return fc_itvec;
}

/*
 * 将两个向量合并为一个
 */
IndexTuple *
gistjoinvector(IndexTuple *fc_itvec, int *fc_len, IndexTuple *fc_additvec, int fc_addlen)
{
	fc_itvec = (IndexTuple *) repalloc((void *) fc_itvec, sizeof(IndexTuple) * ((*fc_len) + fc_addlen));
	memmove(&fc_itvec[*fc_len], fc_additvec, sizeof(IndexTuple) * fc_addlen);
	*fc_len += fc_addlen;
	return fc_itvec;
}

/*
 * 制作普通的IndexTuple向量
 */

IndexTupleData *
gistfillitupvec(IndexTuple *fc_vec, int fc_veclen, int *fc_memlen)
{
	char	   *fc_ptr,
			   *fc_ret;
	int			fc_i;

	*fc_memlen = 0;

	for (fc_i = 0; fc_i < fc_veclen; fc_i++)
		*fc_memlen += IndexTupleSize(fc_vec[fc_i]);

	fc_ptr = fc_ret = palloc(*fc_memlen);

	for (fc_i = 0; fc_i < fc_veclen; fc_i++)
	{
		memcpy(fc_ptr, fc_vec[fc_i], IndexTupleSize(fc_vec[fc_i]));
		fc_ptr += IndexTupleSize(fc_vec[fc_i]);
	}

	return (IndexTupleData *) fc_ret;
}

/*
 * 在IndexTuple向量中创建键的并集（每个索引列一个并集数据）。
 * 并集数据返回到attr/isnull数组中。
 * 结果数据未压缩。
 */
void gistMakeUnionItVec(GISTSTATE *fc_giststate, IndexTuple *fc_itvec, int fc_len,
				   Datum *fc_attr, bool *fc_isnull)
{
	int			fc_i;
	GistEntryVector *fc_evec;
	int			fc_attrsize;

	fc_evec = (GistEntryVector *) palloc((fc_len + 2) * sizeof(GISTENTRY) + GEVHDRSZ);

	for (fc_i = 0; fc_i < fc_giststate->nonLeafTupdesc->natts; fc_i++)
	{
		int			fc_j;

		/* 收集此列的非空数据 */
		fc_evec->n = 0;
		for (fc_j = 0; fc_j < fc_len; fc_j++)
		{
			Datum		fc_datum;
			bool		fc_IsNull;

			fc_datum = index_getattr(fc_itvec[fc_j], fc_i + 1, fc_giststate->leafTupdesc,
								  &fc_IsNull);
			if (fc_IsNull)
				continue;

			gistdentryinit(fc_giststate, fc_i,
						   fc_evec->vector + fc_evec->n,
						   fc_datum,
						   NULL, NULL, (OffsetNumber) 0,
						   false, fc_IsNull);
			fc_evec->n++;
		}

		/* 如果该列全为NULL，并集为NULL */
		if (fc_evec->n == 0)
		{
			fc_attr[fc_i] = (Datum) 0;
			fc_isnull[fc_i] = true;
		}
		else
		{
			if (fc_evec->n == 1)
			{
				/* unionFn可能期望至少两个输入 */
				fc_evec->n = 2;
				fc_evec->vector[1] = fc_evec->vector[0];
			}

			/* 创建并集并存储在attr数组中 */
			fc_attr[fc_i] = FunctionCall2Coll(&fc_giststate->unionFn[fc_i],
										fc_giststate->supportCollation[fc_i],
										PointerGetDatum(fc_evec),
										PointerGetDatum(&fc_attrsize));

			fc_isnull[fc_i] = false;
		}
	}
}

/*
 * 返回一个IndexTuple，包含将“并集”方法应用于指定IndexTuple向量的结果。
 */
IndexTuple gistunion(Relation fc_r, IndexTuple *fc_itvec, int fc_len, GISTSTATE *fc_giststate)
{
	Datum		fc_attr[INDEX_MAX_KEYS];
	bool		fc_isnull[INDEX_MAX_KEYS];

	gistMakeUnionItVec(fc_giststate, fc_itvec, fc_len, fc_attr, fc_isnull);

	return gistFormTuple(fc_giststate, fc_r, fc_attr, fc_isnull, false);
}

/*
 * 形成两个键的并集
 */
void gistMakeUnionKey(GISTSTATE *fc_giststate, int fc_attno,
				 GISTENTRY *fc_entry1, bool fc_isnull1,
				 GISTENTRY *fc_entry2, bool fc_isnull2,
				 Datum *fc_dst, bool *fc_dstisnull)
{
	/* 我们需要一个GistEntryVector，恰好容纳2个元素 */
	union
	{
		GistEntryVector gev;
		char		padding[2 * sizeof(GISTENTRY) + GEVHDRSZ];
	}			fc_storage;
	GistEntryVector *fc_evec = &fc_storage.gev;
	int			fc_dstsize;

	fc_evec->n = 2;

	if (fc_isnull1 && fc_isnull2)
	{
		*fc_dstisnull = true;
		*fc_dst = (Datum) 0;
	}
	else
	{
		if (fc_isnull1 == false && fc_isnull2 == false)
		{
			fc_evec->vector[0] = *fc_entry1;
			fc_evec->vector[1] = *fc_entry2;
		}
		else if (fc_isnull1 == false)
		{
			fc_evec->vector[0] = *fc_entry1;
			fc_evec->vector[1] = *fc_entry1;
		}
		else
		{
			fc_evec->vector[0] = *fc_entry2;
			fc_evec->vector[1] = *fc_entry2;
		}

		*fc_dstisnull = false;
		*fc_dst = FunctionCall2Coll(&fc_giststate->unionFn[fc_attno],
								 fc_giststate->supportCollation[fc_attno],
								 PointerGetDatum(fc_evec),
								 PointerGetDatum(&fc_dstsize));
	}
}

bool gistKeyIsEQ(GISTSTATE *fc_giststate, int fc_attno, Datum fc_a, Datum fc_b)
{
	bool		fc_result;

	FunctionCall3Coll(&fc_giststate->equalFn[fc_attno],
					  fc_giststate->supportCollation[fc_attno],
					  fc_a, fc_b,
					  PointerGetDatum(&fc_result));
	return fc_result;
}

/*
 * 解压所有元组中的键
 */
void gistDeCompressAtt(GISTSTATE *fc_giststate, Relation fc_r, IndexTuple fc_tuple, Page fc_p,
				  OffsetNumber fc_o, GISTENTRY *fc_attdata, bool *fc_isnull)
{
	int			fc_i;

	for (fc_i = 0; fc_i < IndexRelationGetNumberOfKeyAttributes(fc_r); fc_i++)
	{
		Datum		fc_datum;

		fc_datum = index_getattr(fc_tuple, fc_i + 1, fc_giststate->leafTupdesc, &fc_isnull[fc_i]);
		gistdentryinit(fc_giststate, fc_i, &fc_attdata[fc_i],
					   fc_datum, fc_r, fc_p, fc_o,
					   false, fc_isnull[fc_i]);
	}
}

/*
 * 形成oldtup和addtup的并集，如果并集==oldtup则返回NULL
 */
IndexTuple gistgetadjusted(Relation fc_r, IndexTuple fc_oldtup, IndexTuple fc_addtup, GISTSTATE *fc_giststate)
{
	bool		fc_neednew = false;
	GISTENTRY	fc_oldentries[INDEX_MAX_KEYS],
				fc_addentries[INDEX_MAX_KEYS];
	bool		fc_oldisnull[INDEX_MAX_KEYS],
				fc_addisnull[INDEX_MAX_KEYS];
	Datum		fc_attr[INDEX_MAX_KEYS];
	bool		fc_isnull[INDEX_MAX_KEYS];
	IndexTuple	fc_newtup = NULL;
	int			fc_i;

	gistDeCompressAtt(fc_giststate, fc_r, fc_oldtup, NULL,
					  (OffsetNumber) 0, fc_oldentries, fc_oldisnull);

	gistDeCompressAtt(fc_giststate, fc_r, fc_addtup, NULL,
					  (OffsetNumber) 0, fc_addentries, fc_addisnull);

	for (fc_i = 0; fc_i < IndexRelationGetNumberOfKeyAttributes(fc_r); fc_i++)
	{
		gistMakeUnionKey(fc_giststate, fc_i,
						 fc_oldentries + fc_i, fc_oldisnull[fc_i],
						 fc_addentries + fc_i, fc_addisnull[fc_i],
						 fc_attr + fc_i, fc_isnull + fc_i);

		if (fc_neednew)
			/* 我们已经需要新的键，因此可以跳过检查 */
			continue;

		if (fc_isnull[fc_i])
			/* 当且仅当两个键都是NULL时，键的并集可能为NULL */
			continue;

		if (!fc_addisnull[fc_i])
		{
			if (fc_oldisnull[fc_i] ||
				!gistKeyIsEQ(fc_giststate, fc_i, fc_oldentries[fc_i].key, fc_attr[fc_i]))
				fc_neednew = true;
		}
	}

	if (fc_neednew)
	{
		/* 需要更新键 */
		fc_newtup = gistFormTuple(fc_giststate, fc_r, fc_attr, fc_isnull, false);
		fc_newtup->t_tid = fc_oldtup->t_tid;
	}

	return fc_newtup;
}

/*
 * 在上层索引页面中搜索具有最低插入罚金的新索引键“it”的条目。
 *
 * 返回要插入的页面条目的索引。
 */
OffsetNumber gistchoose(Relation fc_r, Page fc_p, IndexTuple fc_it,	/* 它有压缩条目 */
		   GISTSTATE *fc_giststate)
{
	OffsetNumber fc_result;
	OffsetNumber fc_maxoff;
	OffsetNumber fc_i;
	float		fc_best_penalty[INDEX_MAX_KEYS];
	GISTENTRY	fc_entry,
				fc_identry[INDEX_MAX_KEYS];
	bool		fc_isnull[INDEX_MAX_KEYS];
	int			fc_keep_current_best;

	Assert(!GistPageIsLeaf(fc_p));

	gistDeCompressAtt(fc_giststate, fc_r,
					  fc_it, NULL, (OffsetNumber) 0,
					  fc_identry, fc_isnull);

	/* 如果页面为空，我们将返回FirstOffsetNumber（不应该发生） */
	fc_result = FirstOffsetNumber;

	/*
	 * 索引可能有多个列，每列都有一个罚金值。
	 * 在索引定义中较早出现的列的罚金严格比较晚出现的列的罚金更重要。
	 *
	 * best_penalty[j]是我们迄今为止看到的列j的最佳罚金，
	 * 当我们尚未检查列j时为-1。第一个-1右侧的数组条目是未定义的。
	 */
	fc_best_penalty[0] = -1;

	/*
	 * 如果我们发现一个元组与当前最优元组完全一样好，我们可以使用任意一个。当插入许多具有相同或相似键的元组时，尽可能沿着相同的路径下降是更可取的，因为这更友好于缓存。另一方面，如果所有插入在分裂后都落在同一个叶页上，我们将永远不会在分裂的另一半插入任何内容，最终只会使用可用空间的 50%。均匀分布插入将导致更好的空间利用，但这在插入期间会影响缓存局部性。为了兼顾两者，当我们找到一个元组与之前的最佳值完全一样时，随机选择是坚持旧的最佳元组还是使用新的最佳元组。一旦我们决定坚持旧的最佳元组，对于我们可能找到的任何后续同样好的元组，我们将继续坚持使用它。这偏向于偏移量较低的元组，但仍然允许一些插入去到其他同样好的子树。
	 *
	 * keep_current_best 为 -1 如果我们还没有做出随机选择是否保留当前最佳元组。如果我们已经这样做并决定保留它，keep_current_best 为 1；如果我们决定替换，keep_current_best 为 0。 （这个状态会在我们做出替换后重置为 -1，但有时我们会在实际找到替换最佳元组之前提前做出选择。）
	 */
	fc_keep_current_best = -1;

	/*
	 * 循环遍历页面上的元组。
	 */
	fc_maxoff = PageGetMaxOffsetNumber(fc_p);
	Assert(fc_maxoff >= FirstOffsetNumber);

	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
	{
		IndexTuple	fc_itup = (IndexTuple) PageGetItem(fc_p, PageGetItemId(fc_p, fc_i));
		bool		fc_zero_penalty;
		int			fc_j;

		fc_zero_penalty = true;

		/* 遍历索引属性。 */
		for (fc_j = 0; fc_j < IndexRelationGetNumberOfKeyAttributes(fc_r); fc_j++)
		{
			Datum		fc_datum;
			float		fc_usize;
			bool		fc_IsNull;

			/* 计算此列的惩罚。 */
			fc_datum = index_getattr(fc_itup, fc_j + 1, fc_giststate->leafTupdesc,
								  &fc_IsNull);
			gistdentryinit(fc_giststate, fc_j, &fc_entry, fc_datum, fc_r, fc_p, fc_i,
						   false, fc_IsNull);
			fc_usize = gistpenalty(fc_giststate, fc_j, &fc_entry, fc_IsNull,
								&fc_identry[fc_j], fc_isnull[fc_j]);
			if (fc_usize > 0)
				fc_zero_penalty = false;

			if (fc_best_penalty[fc_j] < 0 || fc_usize < fc_best_penalty[fc_j])
			{
				/*
				 * 此列的新最佳惩罚。暂时选择此元组作为目标，并记录最佳惩罚。然后将下一个列的惩罚重置为“未知”（间接地，将所有右侧列的惩罚也重置为“未知”）。这将迫使我们在后续循环迭代中将此元组的惩罚值视为所有剩余列的最佳惩罚。
				 */
				fc_result = fc_i;
				fc_best_penalty[fc_j] = fc_usize;

				if (fc_j < IndexRelationGetNumberOfKeyAttributes(fc_r) - 1)
					fc_best_penalty[fc_j + 1] = -1;

				/* 我们有新的最佳，所以重置保留决定 */
				fc_keep_current_best = -1;
			}
			else if (fc_best_penalty[fc_j] == fc_usize)
			{
				/*
				 * 当前元组在此列的表现与迄今为止看到的最佳元组完全一样。这个循环的下一次迭代将比较下一个列。
				 */
			}
			else
			{
				/*
				 * 当前元组在此列的表现比迄今为止看到的最佳元组差。跳过剩余的列，并移至下一个元组（如果有）。
				 */
				fc_zero_penalty = false;	/* 以便外部循环不会退出 */
				break;
			}
		}

		/*
		 * 如果我们循环到最后一列，且没有更新“结果”，那么此元组与之前的最佳元组完全一样好。
		 */
		if (fc_j == IndexRelationGetNumberOfKeyAttributes(fc_r) && fc_result != fc_i)
		{
			if (fc_keep_current_best == -1)
			{
				/* 我们还没有为这个旧的最佳做出随机选择 */
				fc_keep_current_best = pg_prng_bool(&pg_global_prng_state) ? 1 : 0;
			}
			if (fc_keep_current_best == 0)
			{
				/* 我们选择使用新的元组 */
				fc_result = fc_i;
				/* 如果还有更多完全一样好的元组，重新选择 */
				fc_keep_current_best = -1;
			}
		}

		/*
		 * 如果我们找到了一个对所有列罚款为零的元组，并且我们
		 * 决定不想搜索另一个罚款相等的元组，那么就没有必要检查剩余的元组；直接退出
		 * 循环并返回它即可。
		 */
		if (fc_zero_penalty)
		{
			if (fc_keep_current_best == -1)
			{
				/* 我们还没有为这个旧的最佳做出随机选择 */
				fc_keep_current_best = pg_prng_bool(&pg_global_prng_state) ? 1 : 0;
			}
			if (fc_keep_current_best == 1)
				break;
		}
	}

	return fc_result;
}

/*
 * 用键的解压缩版本初始化一个GiST条目
 */
void gistdentryinit(GISTSTATE *fc_giststate, int fc_nkey, GISTENTRY *fc_e,
			   Datum fc_k, Relation fc_r, Page fc_pg, OffsetNumber fc_o,
			   bool fc_l, bool fc_isNull)
{
	if (!fc_isNull)
	{
		GISTENTRY  *fc_dep;

		gistentryinit(*fc_e, fc_k, fc_r, fc_pg, fc_o, fc_l);

		/* opclass中可能没有解压函数 */
		if (!OidIsValid(fc_giststate->decompressFn[fc_nkey].fn_oid))
			return;

		fc_dep = (GISTENTRY *)
			DatumGetPointer(FunctionCall1Coll(&fc_giststate->decompressFn[fc_nkey],
											  fc_giststate->supportCollation[fc_nkey],
											  PointerGetDatum(fc_e)));
		/* decompressFn可能只是返回给定的指针 */
		if (fc_dep != fc_e)
			gistentryinit(*fc_e, fc_dep->key, fc_dep->rel, fc_dep->page, fc_dep->offset,
						  fc_dep->leafkey);
	}
	else
		gistentryinit(*fc_e, (Datum) 0, fc_r, fc_pg, fc_o, fc_l);
}

IndexTuple gistFormTuple(GISTSTATE *fc_giststate, Relation fc_r,
			  Datum *fc_attdata, bool *fc_isnull, bool fc_isleaf)
{
	Datum		fc_compatt[INDEX_MAX_KEYS];
	IndexTuple	fc_res;

	gistCompressValues(fc_giststate, fc_r, fc_attdata, fc_isnull, fc_isleaf, fc_compatt);

	fc_res = index_form_tuple(fc_isleaf ? fc_giststate->leafTupdesc :
						   fc_giststate->nonLeafTupdesc,
						   fc_compatt, fc_isnull);

	/*
	 * 内部页面上元组的偏移量编号未使用。出于历史原因，
	 * 它设置为0xffff。
	 */
	ItemPointerSetOffsetNumber(&(fc_res->t_tid), 0xffff);
	return fc_res;
}

void gistCompressValues(GISTSTATE *fc_giststate, Relation fc_r,
				   Datum *fc_attdata, bool *fc_isnull, bool fc_isleaf, Datum *fc_compatt)
{
	int			fc_i;

	/*
	 * 对每个属性调用压缩方法。
	 */
	for (fc_i = 0; fc_i < IndexRelationGetNumberOfKeyAttributes(fc_r); fc_i++)
	{
		if (fc_isnull[fc_i])
			fc_compatt[fc_i] = (Datum) 0;
		else
		{
			GISTENTRY	fc_centry;
			GISTENTRY  *fc_cep;

			gistentryinit(fc_centry, fc_attdata[fc_i], fc_r, NULL, (OffsetNumber) 0,
						  fc_isleaf);
			/* opclass中可能没有压缩函数 */
			if (OidIsValid(fc_giststate->compressFn[fc_i].fn_oid))
				fc_cep = (GISTENTRY *)
					DatumGetPointer(FunctionCall1Coll(&fc_giststate->compressFn[fc_i],
													  fc_giststate->supportCollation[fc_i],
													  PointerGetDatum(&fc_centry)));
			else
				fc_cep = &fc_centry;
			fc_compatt[fc_i] = fc_cep->key;
		}
	}

	if (fc_isleaf)
	{
		/*
		 * 如果有的话，放置每个包含的属性。
		 */
		for (; fc_i < fc_r->rd_att->natts; fc_i++)
		{
			if (fc_isnull[fc_i])
				fc_compatt[fc_i] = (Datum) 0;
			else
				fc_compatt[fc_i] = fc_attdata[fc_i];
		}
	}
}

/*
 * 用键字段中获取的值初始化一个GiST条目
 */
static Datum fc_gistFetchAtt(GISTSTATE *fc_giststate, int fc_nkey, Datum fc_k, Relation fc_r)
{
	GISTENTRY	fc_fentry;
	GISTENTRY  *fc_fep;

	gistentryinit(fc_fentry, fc_k, fc_r, NULL, (OffsetNumber) 0, false);

	fc_fep = (GISTENTRY *)
		DatumGetPointer(FunctionCall1Coll(&fc_giststate->fetchFn[fc_nkey],
										  fc_giststate->supportCollation[fc_nkey],
										  PointerGetDatum(&fc_fentry)));

	/* fetchFn设置'key'，将其返回给调用者 */
	return fc_fep->key;
}

/*
 * 获取元组中的所有键。
 * 返回一个包含最初索引数据的新HeapTuple。
 */
HeapTuple gistFetchTuple(GISTSTATE *fc_giststate, Relation fc_r, IndexTuple fc_tuple)
{
	MemoryContext fc_oldcxt = MemoryContextSwitchTo(fc_giststate->tempCxt);
	Datum		fc_fetchatt[INDEX_MAX_KEYS];
	bool		fc_isnull[INDEX_MAX_KEYS];
	int			fc_i;

	for (fc_i = 0; fc_i < IndexRelationGetNumberOfKeyAttributes(fc_r); fc_i++)
	{
		Datum		fc_datum;

		fc_datum = index_getattr(fc_tuple, fc_i + 1, fc_giststate->leafTupdesc, &fc_isnull[fc_i]);

		if (fc_giststate->fetchFn[fc_i].fn_oid != InvalidOid)
		{
			if (!fc_isnull[fc_i])
				fc_fetchatt[fc_i] = fc_gistFetchAtt(fc_giststate, fc_i, fc_datum, fc_r);
			else
				fc_fetchatt[fc_i] = (Datum) 0;
		}
		else if (fc_giststate->compressFn[fc_i].fn_oid == InvalidOid)
		{
			/*
			 * 如果opclass不提供可能改变
			 * 原始值的压缩方法，则att必须以原始形式存储。
			 */
			if (!fc_isnull[fc_i])
				fc_fetchatt[fc_i] = fc_datum;
			else
				fc_fetchatt[fc_i] = (Datum) 0;
		}
		else
		{
			/*
			 * 此列不支持仅索引扫描。由于计划者无论如何选择了仅索引扫描，
			 * 因此它对这一列不感兴趣，我们可以用NULL替换它。
			 */
			fc_isnull[fc_i] = true;
			fc_fetchatt[fc_i] = (Datum) 0;
		}
	}

	/*
	 * 获取每个包含的属性。
	 */
	for (; fc_i < fc_r->rd_att->natts; fc_i++)
	{
		fc_fetchatt[fc_i] = index_getattr(fc_tuple, fc_i + 1, fc_giststate->leafTupdesc,
									&fc_isnull[fc_i]);
	}
	MemoryContextSwitchTo(fc_oldcxt);

	return heap_form_tuple(fc_giststate->fetchTupdesc, fc_fetchatt, fc_isnull);
}

float gistpenalty(GISTSTATE *fc_giststate, int fc_attno,
			GISTENTRY *fc_orig, bool fc_isNullOrig,
			GISTENTRY *fc_add, bool fc_isNullAdd)
{
	float		fc_penalty = 0.0;

	if (fc_giststate->penaltyFn[fc_attno].fn_strict == false ||
		(fc_isNullOrig == false && fc_isNullAdd == false))
	{
		FunctionCall3Coll(&fc_giststate->penaltyFn[fc_attno],
						  fc_giststate->supportCollation[fc_attno],
						  PointerGetDatum(fc_orig),
						  PointerGetDatum(fc_add),
						  PointerGetDatum(&fc_penalty));
		/* 不允许负的或NaN罚款 */
		if (isnan(fc_penalty) || fc_penalty < 0.0)
			fc_penalty = 0.0;
	}
	else if (fc_isNullOrig && fc_isNullAdd)
		fc_penalty = 0.0;
	else
	{
		/* 尝试防止混合空值和非空值 */
		fc_penalty = get_float4_infinity();
	}

	return fc_penalty;
}

/*
 * 初始化一个新的索引页面
 */
void gistinitpage(Page fc_page, uint32 fc_f)
{
	GISTPageOpaque fc_opaque;

	PageInit(fc_page, BLCKSZ, sizeof(GISTPageOpaqueData));

	fc_opaque = GistPageGetOpaque(fc_page);
	fc_opaque->rightlink = InvalidBlockNumber;
	fc_opaque->flags = fc_f;
	fc_opaque->gist_page_id = GIST_PAGE_ID;
}

/*
 * 初始化一个新的索引缓冲区
 */
void GISTInitBuffer(Buffer fc_b, uint32 fc_f)
{
	Page		fc_page;

	fc_page = BufferGetPage(fc_b);
	gistinitpage(fc_page, fc_f);
}

/*
 * 验证刚读取的页面是否正常。
 */
void gistcheckpage(Relation fc_rel, Buffer fc_buf)
{
	Page		fc_page = BufferGetPage(fc_buf);

	/*
	 * ReadBuffer验证每个新读取的页面是否通过
	 * PageHeaderIsValid，这意味着它要么包含一个相当正常的
	 * 页面头，要么全为零。然而，我们必须防范全零
	 * 的情况。
	 */
	if (PageIsNew(fc_page))
		ereport(ERROR,
				(errcode(ERRCODE_INDEX_CORRUPTED),
				 errmsg("index \"%s\" contains unexpected zero page at block %u",
						RelationGetRelationName(fc_rel),
						BufferGetBlockNumber(fc_buf)),
				 errhint("Please REINDEX it.")));

	/*
	 * 另外检查特殊区域是否正常。
	 */
	if (PageGetSpecialSize(fc_page) != MAXALIGN(sizeof(GISTPageOpaqueData)))
		ereport(ERROR,
				(errcode(ERRCODE_INDEX_CORRUPTED),
				 errmsg("index \"%s\" contains corrupted page at block %u",
						RelationGetRelationName(fc_rel),
						BufferGetBlockNumber(fc_buf)),
				 errhint("Please REINDEX it.")));
}


/*
 * 分配一个新页面（通过回收或扩展索引文件）
 *
 * 返回的缓冲区已经被固定并排他锁定
 *
 * 调用者负责通过调用GISTInitBuffer初始化页面
 */
Buffer gistNewBuffer(Relation fc_r)
{
	Buffer		fc_buffer;
	bool		fc_needLock;

	/* 首先，尝试从 FSM 获取一个页面 */
	for (;;)
	{
		BlockNumber fc_blkno = GetFreeIndexPage(fc_r);

		if (fc_blkno == InvalidBlockNumber)
			break;				/* FSM中没有剩余 */

		fc_buffer = ReadBuffer(fc_r, fc_blkno);

		/*
		 * 我们必须防止其他人已经回收此页面的可能性；
		 * 如果这样，缓冲区可能会被锁定。
		 */
		if (ConditionalLockBuffer(fc_buffer))
		{
			Page		fc_page = BufferGetPage(fc_buffer);

			/*
			 * 如果页面从未初始化，则可以使用它。
			 */
			if (PageIsNew(fc_page))
				return fc_buffer;

			gistcheckpage(fc_r, fc_buffer);

			/*
			 * 否则，如果被删除且太旧以至于没有
			 * 进程对此感兴趣，则回收它。
			 */
			if (gistPageRecyclable(fc_page))
			{
				/*
				 * 如果我们正在为热备份生成WAL，则创建一个WAL
				 * 记录，这将允许我们与在备份上运行的查询发生冲突，
				 * 以防它们的快照早于
				 * 页面删除的XID。
				 */
				if (XLogStandbyInfoActive() && RelationNeedsWAL(fc_r))
					gistXLogPageReuse(fc_r, fc_blkno, GistPageGetDeleteXid(fc_page));

				return fc_buffer;
			}

			LockBuffer(fc_buffer, GIST_UNLOCK);
		}

		/* 不能使用，因此释放缓冲区并重试 */
		ReleaseBuffer(fc_buffer);
	}

	/* 必须扩展文件 */
	fc_needLock = !RELATION_IS_LOCAL(fc_r);

	if (fc_needLock)
		LockRelationForExtension(fc_r, ExclusiveLock);

	fc_buffer = ReadBuffer(fc_r, P_NEW);
	LockBuffer(fc_buffer, GIST_EXCLUSIVE);

	if (fc_needLock)
		UnlockRelationForExtension(fc_r, ExclusiveLock);

	return fc_buffer;
}

/* 这个页面还可以被回收吗？ */
bool gistPageRecyclable(Page fc_page)
{
	if (PageIsNew(fc_page))
		return true;
	if (GistPageIsDeleted(fc_page))
	{
		/*
		 * 页面已被删除，但什么时候删除的？如果只是被删除，扫描
		 * 可能已经看到了它的下行连接，并将在稍后读取页面。
		 * 只要这种情况可能发生，我们就必须将已删除的页面保留为
		 * 墓碑。
		 *
		 * 因此，检查删除的 XID 是否仍然对任何人可见。如果不可见，
		 * 那么正在进行的扫描就不可能看到它的下行连接，我们可以回收它。
		 */
		FullTransactionId fc_deletexid_full = GistPageGetDeleteXid(fc_page);

		return GlobalVisCheckRemovableFullXid(NULL, fc_deletexid_full);
	}
	return false;
}

bytea * gistoptions(Datum fc_reloptions, bool fc_validate)
{
	static const relopt_parse_elt fc_tab[] = {
		{"fillfactor", RELOPT_TYPE_INT, offsetof(GiSTOptions, fillfactor)},
		{"buffering", RELOPT_TYPE_ENUM, offsetof(GiSTOptions, buffering_mode)}
	};

	return (bytea *) build_reloptions(fc_reloptions, fc_validate,
									  RELOPT_KIND_GIST,
									  sizeof(GiSTOptions),
									  fc_tab, lengthof(fc_tab));
}

/*
 *	gistproperty() -- 检查索引的布尔属性。
 *
 * 这对大多数 AM 来说是可选的，但对于 GiST 来说是必需的，因为核心
 * 属性代码不支持 AMPROP_DISTANCE_ORDERABLE。我们还在这里处理
 * AMPROP_RETURNABLE，以避免打开关系以调用 gistcanreturn。
 */
bool gistproperty(Oid fc_index_oid, int fc_attno,
			 IndexAMProperty fc_prop, const char *fc_propname,
			 bool *fc_res, bool *fc_isnull)
{
	Oid			fc_opclass,
				fc_opfamily,
				fc_opcintype;
	int16		fc_procno;

	/* 仅回答列级查询 */
	if (fc_attno == 0)
		return false;

	/*
	 * 当前，GiST 距离排序扫描要求操作类中有一个距离
	 * 函数，并使用默认类型（即，加载到 relcache 条目中的
	 * 函数，参见 initGISTstate）。因此，我们假设如果存在这样的
	 * 函数，那么必定有其存在的理由（而不是翻遍所有的操作族
	 * 的操作符以找到一个有序的）。
	 *
	 * 本质上相同的代码可以测试我们是否支持返回列数据，
	 * 因为如果操作类提供了获取过程，这就是真的。
	 */

	switch (fc_prop)
	{
		case AMPROP_DISTANCE_ORDERABLE:
			fc_procno = GIST_DISTANCE_PROC;
			break;
		case AMPROP_RETURNABLE:
			fc_procno = GIST_FETCH_PROC;
			break;
		default:
			return false;
	}

	/* 首先，我们需要知道列的操作类。 */
	fc_opclass = get_index_column_opclass(fc_index_oid, fc_attno);
	if (!OidIsValid(fc_opclass))
	{
		*fc_isnull = true;
		return true;
	}

	/* 现在查找操作类的族和输入数据类型。 */
	if (!get_opclass_opfamily_and_input_type(fc_opclass, &fc_opfamily, &fc_opcintype))
	{
		*fc_isnull = true;
		return true;
	}

	/* 现在我们可以检查是否提供函数。 */

	*fc_res = SearchSysCacheExists4(AMPROCNUM,
								 ObjectIdGetDatum(fc_opfamily),
								 ObjectIdGetDatum(fc_opcintype),
								 ObjectIdGetDatum(fc_opcintype),
								 Int16GetDatum(fc_procno));

	/*
	 * 特殊情况：即使没有获取函数，如果操作类没有压缩函数，
	 * AMPROP_RETURNABLE 也为真。
	 */
	if (fc_prop == AMPROP_RETURNABLE && !*fc_res)
	{
		*fc_res = !SearchSysCacheExists4(AMPROCNUM,
									  ObjectIdGetDatum(fc_opfamily),
									  ObjectIdGetDatum(fc_opcintype),
									  ObjectIdGetDatum(fc_opcintype),
									  Int16GetDatum(GIST_COMPRESS_PROC));
	}

	*fc_isnull = false;

	return true;
}

/*
 * 一些索引不是 WAL 记录的，但我们仍然需要 LSN 来检测并发页面
 * 拆分。本函数提供了一系列假 LSN 以供这个目的。
 */
XLogRecPtr gistGetFakeLSN(Relation fc_rel)
{
	if (fc_rel->rd_rel->relpersistence == RELPERSISTENCE_TEMP)
	{
		/*
		 * 临时关系仅在我们的会话中可访问，因此简单的
		 * 后端本地计数器就可以了。
		 */
		static XLogRecPtr fc_counter = FirstNormalUnloggedLSN;

		return fc_counter++;
	}
	else if (RelationIsPermanent(fc_rel))
	{
		/*
		 * 对于此关系，WAL 记录将在提交后开始，因此它的 LSN
		 * 必须是比下一个提交的 LSN 更小的不同数字。
		 * 如果插入 LSN 在最后一次调用后没有推进，
		 * 则发出一个虚拟的 WAL 记录。
		 */
		static XLogRecPtr fc_lastlsn = InvalidXLogRecPtr;
		XLogRecPtr	fc_currlsn = GetXLogInsertRecPtr();

		/* 不应为 WAL 记录的关系调用此函数 */
		Assert(!RelationNeedsWAL(fc_rel));

		/* 如果我们已经有一个不同的 LSN，则不需要实际记录 */
		if (!XLogRecPtrIsInvalid(fc_lastlsn) && fc_lastlsn == fc_currlsn)
			fc_currlsn = gistXLogAssignLSN();

		fc_lastlsn = fc_currlsn;
		return fc_currlsn;
	}
	else
	{
		/*
		 * 未记录的关系可以从其他后端访问，并且在
		 * （干净）重启后仍然存在。GetFakeLSNForUnloggedRel() 为我们处理这一点。
		 */
		Assert(fc_rel->rd_rel->relpersistence == RELPERSISTENCE_UNLOGGED);
		return GetFakeLSNForUnloggedRel();
	}
}
